class Node {
  constructor(element) {
    // 保存元素
    this.element = element;
    // 指向下一个节点
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // *1.append:追加方法
  append(element) {
    // 1.创建一个节点
    const newNode = new Node(element);

    // 2.追加
    // 2.1没有节点的情况
    if (this.length === 0) {
      this.head = newNode;
    }
    // 2.2有节点的情况
    else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }

    this.length++;
  }

  // *2.insert:插入方法
  insert(position, element) {
    // 1.越界判断
    if (position < 0 || position > this.length) return false;

    // 2.创建节点
    const newNode = new Node(element);

    // 3.插入判断
    // 第一个节点
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    }
    // 非第一个节点
    else {
      let index = 0;
      let current = this.head;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = newNode;
      newNode.next = current;
    }

    this.length++;
    return true;
  }

  // *3.get:获取对应位置的元素
  get(position) {
    // 1.越界判断
    if (position < 0 || position > this.length - 1) return null;

    // 2.查询对应位置的元素
    let index = 0;
    let current = this.head;
    while (index++ < position) {
      current = current.next;
    }

    return current.element;
  }

  // *4.indexOf:返回元素在链表中的索引,如果没有返回-1
  indexOf(element) {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }

    return -1;
  }

  // *5.update:修改某个位置的元素
  update(position, element) {
    const result = this.removeAt(position);
    this.insert(position, element);
    return result;
  }

  // *6.removeAt:删除某个位置的元素
  removeAt(position) {
    // 1.越界判断
    if (position < 0 || position > this.length - 1) return null;

    // 2.删除元素
    let current = this.head;
    let previous = null;
    let index = 0;

    if (position === 0) {
      this.head = current.next;
    } else {
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
    }

    this.length--;
    return current.element;
  }

  // *7.remove:从链表中移除一项
  remove(element) {
    // 1.获取元素位置
    const index = this.indexOf(element);
    if (index === -1) return;
    this.length--;
    return this.removeAt(index);
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

// *双向链表
class DoublyNode extends Node {
  constructor(element) {
    super(element);
    // 指向前一个节点
    this.prev = null;
  }
}

class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
    // 指向最后一个节点
    this.tail = null;
  }

  append(element) {
    // 创建节点
    const newNode = new DoublyNode(element);

    // 追加元素
    if (this.length === 0) {
      this.tail = newNode;
      this.head = newNode;
    }
    // 原来有元素
    else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
  }

  insert(position, element) {
    // 越界判断
    if (position < 0 || position > this.length) return false;
    // 创建节点
    const newNode = new DoublyNode(element);
    // 判断多种插入情况

    // 在头部插入
    if (position === 0) {
      // 链表中没有任何节点
      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      }
      // 链表中有节点
      else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
    }
    // 插入最后一个位置
    else if (position === this.length) {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    // 在链表元素中间插入节点
    else {
      // 当前链表位置的索引
      let index = 0;
      // 当前链表节点
      let current = this.head;
      // 当前链表节点的上一个节点
      let previous = null;

      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      // 交换节点信息
      previous.next = newNode;
      newNode.prev = previous;
      newNode.next = current;
      current.prev = newNode;
    }
    this.length++;
    return true;
  }

  removeAt(position) {
    // 越界判断
    if (position < 0 || position > this.length - 1) return false;
    // 判断节点位置
    let current = this.head;
    if (position === 0) {
      // 节点只有一个
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      }
      // 节点不只有一个
      else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    }
    // 要删的节点是最后一个
    else if (position === this.length - 1) {
      current = this.tail;
      this.tail.prev.next = null;
      this.tail = this.tail.prev;
    }
    // 删除的节点是中间的
    else {
      let index = 0;
      let previous = null;
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }

    this.length--;
    return current.element;
  }
}

const Doubly = new DoublyLinkedList();
Doubly.append('666');
Doubly.append('999');
Doubly.append('elysia');
Doubly.insert(1, 'cool');
console.log('removeAt', Doubly.removeAt(1));
console.log('get', Doubly.get(1));
console.log(Doubly);
